C/C++ Users Group Library 1996 July/C-C++ Users Group Library July 1996.iso/vol_200/288_01/knauss.txt

Text File | 1989-05-23 | 14KB | 239 lines

A Poor Man's Solution to the Traveling Salesman Problem

Kevin E Knauss

12 Mar 89

Given a map and a means of transportation, a competent traveling
salesman can pick a reasonable route to all his customers. The route he
picks needn't be optimal just practical. In this article, we'll explore
a hypothetical salesman's intuitive approach to finding a practical
route to all his customers and its implementation in the C programming
language. In an attempt to find elegant optimal solutions to tough
problems, we often overlook solutions which appear to be rather
"brutish." Upon closer inspection, however, we see that these solutions
are more elegant than they appear and, better yet, they work!

BACKGROUND

Routing and scheduling problems are inherently difficult to solve
because they often require total enumeration of all possible outcomes.
As the number of data points in the problem increases, the possible
outcomes increase exponentially. With the Traveling Salesman Problem
(TSP) for instance, studies have shown that an algorithm which yields an
exact solution is relatively infeasible for networks containing in
excess of 100 points. In fact, there are problems with as few as 48
cities for which the best answer found has not been proven to be
optimal. By using heuristics of various types, one is enabled to find
feasible (though not necessarily optimal) solutions to these otherwise
"unsolvable" problems.

The TSP simply stated is: "A salesman, starting in one city, wishes to
visit each n─1 other cities once and only once and return to the start.
In what order should he visit the cities to minimize the total distance
traveled?" (8) This may seem too trivial a task to have generated active
research for over three decades (the literature I've researched goes
back to 1958), but there are many practical applications for the
solution of this basic problem. Automated drilling machines and the
newer laser drills used to drill printed circuit boards, for example,
may have hundreds or thousands of holes to drill and often spend as much
time traveling to a position for a hole as they do drilling it.
Programming efficient head travel for these machines could make the
difference for a company to turn a profit or loss. Solve the more basic
TSP, and the marginal printed circuit board company may be able to stay
in business by applying the same techniques.

The TSP is one which is, to quote an old cliche, "easier said than
done." That is, it is easy to explain the problem but difficult to
solve; at least it seems difficult to solve when we look at many of the
purely mathematical models that are, too often, not related back to the
original problem. I chose to attack the TSP in a simplistic manner in
an attempt to find one or more algorithms which would approximate a
person's intuitive approach. In so doing, I was able to find an
efficient way to "solve" the problem by producing acceptable results to
large─scale traveling salesman problems. (Note that the word
"acceptable" implies that judgments are required.)

TERMINOLOGY

Before we begin traveling around, a review of TSP terminology is in
order. We'll begin with the city, our most basic term. This is what
will be visited and may also be referred to as a town, point, node, or
vertex. One goes from one city to the next by traveling a given
distance or incurring a specified cost. The terms link, arc, and edge
are also used in place of distance or cost. The collection of all the
cities and the distances between each pair is a network or graph and is
often represented by a distance matrix. A salesman will follow a route
to visit each of the cities in the network, and this route may also be
called a tour, path, or circuit. Finally, if we remove two or more
links from the completed tour, we will break it into sub─paths or chains
of cities.

The distance matrix is a two dimensional array where the horizontal or
row vector (dimension) is identical to the vertical or column vector.
The cell found at each intersection contains the distance or cost
between the city represented by the horizontal coordinate and the city
represented by the vertical coordinate. Those familiar with graph
theory haven't seen anything new here. If you've seen a lot of these
terms for the first time, however, don't be afraid to refer back, for
I'll be using many of them interchangeably.

APPROACH

Let's now consider the problem in terms of a salesman who must visit a
dozen or so cities in the state of Hypothetica. Since the salesman must
leave and return to the same city and visit all other cities in the
process, his tour will be some sort of loop through the state.
Obviously, as a loop is unbroken, one may start at any point on the the
tour and still trace the same loop. Thus the starting city is of no
consequence; rather we want to find the best route irregardless of the
salesman's starting point.

Intuitively, one would want to travel to cities nearby and to cities
near those. We can build a procedure based on this thought by first
finding the closest two cities and then continuing to the next closest
city that hasn't been visited. This should produce a fairly good tour,
or at least would seem so at first. It may turn out that this tour
isn't optimal, but it's a reasonable solution for starters.

As the cities are exhausted from our network, we have fewer choices to
make. Intuitively, we may reason that the choices left to us may not be
as good as those we're offered in the early stages of tour building.
Our salesman may be forced to backtrack and cross previously traversed
arcs. If we check the proximity of neighboring cities, however,
especially those near the end of the initial tour, we may be able to
find improvements.

One approach we may try involves the removal of a single city from the
tour and testing it between each pair of cities in the remaining tour.
Once we've tested it in each location, we'll place it in the location
where the overall circuit cost is lowest (i.e. the shortest distance
the salesman must travel). This same approach may be tried with chains
of cities of varying lengths, but with chains we must also check for
orientation (that is try the chain both frontward and backward between
each pair of cities). This leaves us with our last thought of simply
checking the orientation of a chain in its original location. If you
think a picture is worth a thousand words, see Figure 1 so we can cut
4,000 words from this article. By testing the proximity of every city
or the proximity and orientation of every chain, we can be fairly
confident that any ill effects produced by our original technique will
be cleaned up.

If we look through related literature, we find that our tour building
and improvement techniques have already been studied and named. Our
tour building algorithm is known as the nearest neighbor or greedy
algorithm. Our tour improvement algorithms generally fall into a
category known as k─optimality or k─opt for short. A tour is said to be
k─optimal if we are unable to improve it by removing any k arcs and
replacing them with k others. Checking chain orientation in place is
the same as removing two arcs and replacing them with two others and is
thus the 2─opt algorithm. Likewise, chain proximity and orientation is
the 3─opt algorithm with point proximity a special case where the chain
to be tested has length one. Even though these improvement techniques
are related, we'll evaluate each on its own merits.

IMPLEMENTATION

To evaluate the intuitive approach we may embark upon an elaborate
mathematical analysis that may or may not produce any conclusive
results, or we may implement the solutions in practical models that may
be run against live data. If this was a scientific journal, we'd follow
the mathematical tack; but since this is a practical journal, we'll try
the modeling approach.

The main functions are programmed in their own modules called:
NearNeighbor, PointOpt, TwoOpt, Hybrid, and ThreeOpt (listings 1 through
5 respectively). NearNeighbor generates